package rpg.util;

import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import rpg.Location;
import rpg.Maps.Map;
import rpg.Maps.MapTile;

/**
 * rothens.tarhely.biz
 * @author Rothens
 */
public class AStar {

	public class Node {

		public Node parent;
		public Location location;
		public int moveCostFrom;
		int moveCostTo;
		public int allCost;

		public Node(Node parent, Location location) {
			this.parent = parent;
			this.location = location;
			if (parent == null) {
				moveCostFrom = 0;
			}
			calculateTo(endLocation);


		}

		public void setParent(Node parent) {
			if (parent == null) {
				return;
			}
			this.parent = parent;
			this.moveCostFrom = parent.moveCostFrom + 1;
		}

		public void calculateTo(Location to) {
			int dist = 0;
			dist += Math.abs(location.getTileX() - to.getTileX());
			dist += Math.abs(location.getTileY() - to.getTileY());
			moveCostTo = dist;
			allCost = moveCostTo + moveCostFrom;
		}
	}
	
	private Node closest;
	private List<Node> openSet;
	private List<Node> closedSet;
	Node startNode;
	Location endLocation;
	Map map;

	private Node getClosestNode() {
		Iterator<Node> it = openSet.iterator();
		Node ret = null;
		while (it.hasNext()) {
			Node next = it.next();
			if (ret == null) {
				ret = next;
			}
			if (ret.allCost >= next.allCost) {
				ret = next;
			}
		}
		return ret;
	}

	/**
	 * Tries to get a Node from the closedSet
	 * @param loc location to check
	 * @return Node, or null if not contained
	 */
	private Node getFromClosed(Location loc) {
		Iterator<Node> it = closedSet.iterator();
		Node ret = null;
		while (it.hasNext()) {

			ret = it.next();
			if (ret.location.equals(loc)) {
				return ret;
			}
		}
		return null;
	}

	/**
	 * Tries to get a Node from the openSet
	 * @param loc location to check
	 * @return Node, or null if not contained
	 */
	private Node getFromOpened(Location loc) {
		Iterator<Node> it = openSet.iterator();
		Node ret = null;
		while (it.hasNext()) {
			ret = it.next();
			if (ret.location.equals(loc)) {
				return ret;
			}
		}
		return null;
	}

	private boolean isTheEnd(Node n) {
		int nX = n.location.getTileX();
		int nY = n.location.getTileY();
		int cX = endLocation.getTileX();
		int cY = endLocation.getTileY();
		return (nX == cX && nY == cY);
	}

	private Node generatePath() {
		while (!openSet.isEmpty()) {
			Node next = getClosestNode();
			openSet.remove(next);
			closedSet.add(next);
			for (int i = 0; i < 4; i++) {
				Node toCheck = getTile(next.location, i, map);
				if (toCheck == null) {
					continue;
				}
				if (getFromClosed(toCheck.location) != null) {
					continue;
				}


				Node cont;
				if ((cont = getFromOpened(toCheck.location)) != null) {
					if (cont.moveCostFrom > next.moveCostFrom + 1) {
						cont.setParent(next);
					} else {
						continue;
					}
				} else {
					toCheck.setParent(next);
					openSet.add(toCheck);
				}
				if(toCheck.moveCostTo < closest.moveCostTo) closest = toCheck;
				if (isTheEnd(toCheck)) {

					return toCheck;
				}
			}

		}

		return closest;
	}

	public Node getTile(Location location, int dir, Map map) {
		int tile = location.getTile(dir);
		if (tile == -1) {
			return null;
		}
		Location l = new Location(tile, map);
		MapTile mt = map.tiles[tile];
		if (!mt.isPassable()) {
			return null;
		}
		Node ret = new Node(null, l);

		return ret;

	}

	public LinkedList<Location> getPath(Location from, Location to, Map map) {
		openSet = new LinkedList<Node>();
		closedSet = new LinkedList<Node>();
		endLocation = to;

		startNode = new Node(null, from);
		closest = startNode;
		openSet.add(startNode);

		this.map = map;
		Node generatePath = generatePath();
		if (generatePath != null) {
			LinkedList<Location> ret = new LinkedList<Location>();
			Node par = generatePath;
			Location loc = par.location;
			ret.add(0, loc);

			while (par.parent != null) {
				par = par.parent;
				loc = par.location;
				ret.add(0, loc);

			}
			return ret;

		} else {
			
		}

		return null;
	}
}
